// Author : Zhuowen Tu
/*
    This header file defines all the classes corresponding to the components of which
	the graph is formed. A entire graph is composed of many regions, which are formed
	by contour segments. A region will possibly have many holes whose Ids are denoted
	by hole array in region class. Each contour segment remembers it two extreme vertices and may
	be shared at most by two regions. The left region and right region Ids are stored in
	each contour segment object as well. Each vertex is explictly expressed by a vertex
	object. Besides this, a node object is reduntauntly associated with each vertix, where
	the same 2d corrdinates are saved.
*/

#ifndef _MCMC_LAYERREGION_ELEMENT_H
#define _MCMC_LAYERREGION_ELEMENT_H

#include "mcRand.h"
#include "mcRasterColor.h"
#include "mcLinkList.h"
#include "mcmcRegionImage.h"
#include "mcmcRegionModel.h"
#include "mcmcAffinityMap.h"
#include "mcmcLowLevelStat4Affinity.h"

#define	SHIFT_GREGION		2000
#define PRIOR_SHAPE			0.4
#define PRIOR_REGION		35.0


class MCMC_Layer_Regions;
class MCMC_Contour_Segment;
typedef int* INT_POINTER;

/////////////////////////////////////////////////////////////
// dynamic space
class MCMC_DynamicSpace
{
public:
	// construction & destruction
	MCMC_DynamicSpace();
	~MCMC_DynamicSpace();
	virtual void	Free(void);
	virtual void	Init(void);

	// operators
	MCMC_DynamicSpace&	operator=(const MCMC_DynamicSpace&a);
	friend ofstream &	operator>>(MCMC_DynamicSpace &s, ofstream &strm);
	friend ifstream &	operator<<(MCMC_DynamicSpace &s, ifstream &strm);

	// operations
	inline	void	Empty(void){num_active=0;};
	virtual void	GrowSpaceTo(const int max_num);
	virtual bool	Add(const int id);
	virtual bool	Delete(const int id, const int id_replace=-1);
	virtual int	GetFirst(void);
	virtual int	GetNext(void);
	inline	int	Num(void) const {return num_active;};
	virtual bool	Exist(const int id) const;
	inline	int	Data(const int i){return p_data[i];};

protected:
	int	*p_data;
	int	max_space;
	int	num_active;

private:
	int	current;
};


/* coordinates system

-----------> (column, y)
|
|
|
|
V (row, x)

I may interchange the definitino of x and y in some other
file, which makes the code a little bit confusing.

  Pixel neighborhood relationships are defined as four neighbor system.
*/

///////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////
// manage nodes for vertices, contour segments, regions, and groups
class MCMC_MemoryNode
{
public:
	// construction & destruction
	MCMC_MemoryNode(){;};
	~MCMC_MemoryNode(){;};

	// operators
	friend ofstream & operator>>(MCMC_MemoryNode &n, ofstream &strm)
	{
		strm.write((char*)&(n.next), sizeof(n.next));
		strm.write((char*)&(n.last), sizeof(n.last));

		return strm;
	}
	friend ifstream & operator<<(MCMC_MemoryNode &n, ifstream &strm)
	{
		strm.read((char*)&(n.next), sizeof(n.next));
		strm.read((char*)&(n.last), sizeof(n.last));

		return strm;
	}

public:
	int		next;
	int		last;
};

class MCMC_MemoryNodeManagement
{
public:
	// construction & destruction
	MCMC_MemoryNodeManagement();
	~MCMC_MemoryNodeManagement();

	virtual void	Empty(void);

		MCMC_MemoryNodeManagement&	operator=(const MCMC_MemoryNodeManagement& a);
		friend	ofstream & operator>>(MCMC_MemoryNodeManagement &n, ofstream &strm);
		friend	ifstream & operator<<(MCMC_MemoryNodeManagement &n, ifstream &strm);
	// operations
	virtual void	Set(MCMC_MemoryNode *p_nodes1, const int max_num, const char by_type1);
	virtual void	Init(MCMC_MemoryNode *p_nodes1, const int max_num, const char by_type1);
	virtual int		New(void);
	virtual bool	Delete(const int id);

	inline	int		Num(void) const {return num_of_nodes;};
	inline	int		Max(void) const {return max_space;};
	inline	int		GetFirst(void);
	inline	int		GetNext(void);

private:
	inline	MCMC_MemoryNode* GetNode(const int i);

public:
	int				current;

protected:
	int				head,tail;
	int				num_of_nodes;		// number of active nodes
	int				head_node_new;
	int				max_space;

private:
	char			by_type;

	MCMC_MemoryNode *p_nodes;
};


/////////////////////////////////////////////////////////////
//This class defines node objects that form contour segments.

class MCMC_Node :public MCMC_MemoryNode
{
public:
	// construction & destruction
	MCMC_Node(){link[0]=-1;link[1]=-1;};
	~MCMC_Node(){link[0]=-1;link[1]=-1;};

	inline void		Empty(void){link[0]=-1;link[1]=-1;};

	// operators
	MCMC_Node &	operator=(const MCMC_Node &a);
	friend ofstream &	operator>>(MCMC_Node &n, ofstream &strm);
	friend ifstream &	operator<<(MCMC_Node &n, ifstream &strm);

	// operations
	inline float	GetX(void){return x;};					//row
	inline float	GetY(void){return y;};					//col
	inline int		GetRow(void){return int(x+0.5);};
	inline int		GetCol(void){return int(y+0.5);};
	inline void		SetX(const double value){x = (float)value;};
	inline void		SetY(const double value){y = (float)value;};
	inline int		GridRow(void){return IntClose(x);};
	inline int		GridCol(void){return IntClose(y);};

	virtual double	TotalCodingBits(void);

public:
	int	link[2];		//link[0]--next node, link[1]--last node

private:
	float	x,y;			//row=x+0.5 col=y+0.5
};

/////////////////////////////////////////////////////////////////////////////
//This class defines vertex objects to which contour segments are connected.
//Given a vertex, all the contour segments that connect to it could
//  be traced one by one.

class MCMC_Vertex :public MCMC_MemoryNode
{
public:
	// construction & destruction
	MCMC_Vertex();
	~MCMC_Vertex();

	void	Init(void);
	void	Empty(void);

	// operator
	MCMC_Vertex &	operator=(const MCMC_Vertex &a);
	friend ofstream &		operator>>(MCMC_Vertex &v, ofstream &strm);
	friend ifstream &		operator<<(MCMC_Vertex &s, ifstream &strm);

	// access
	inline float		GetX(void){return x;};
	inline float		GetY(void){return y;};
	inline int			GetRow(void){return int(x+0.5);};
	inline int			GetCol(void){return int(y+0.5);};
	inline int			GridRow(void){return IntClose(x);};
	inline int			GridCol(void){return IntClose(y);};
	inline void			SetX(const double value){x = (float)value;};
	inline void			SetY(const double value){y = (float)value;};
	inline	int		Degree(void) const {return degree;};	// total degree meaning how many contour segments connect to this vertex
	virtual int			DegreeExt(void);						// total degree with self-closed contour counted as two
	inline	MCMC_Layer_Regions* LayerRegion(void){return player_region;};
	inline  void        SetLayerRegion(MCMC_Layer_Regions *player_region1) {player_region = player_region1;};
	inline	int			KeepCurrent(void){return current_cseg;};
	inline	void		RestoreCurrent(const int a){current_cseg=a;};
	inline	int			Id(){return id;};
	inline	void		SetId(int i){id=i;};
	inline  bool		Valid(void) const {if(degree>0 && degree<200)return true;else return false;};
	int				GetFirstCSeg(void);	// clockwise
	int	 			GetNextCSeg(void);	// clockwise
	virtual void		GetCSegOfAtomicRegion(mcmcVector<int> &vc_csegs, const int id_region, const int side=0);	// side 0: right  1:left
	virtual void		GetCSegOfGRegion(mcmcVector<int> &vc_csegs, const int id_gregion, const int side=0);	// side 0: right  1:left
	virtual int		TotalCodingBits(void);

	// operations
	int		AddSeg(const int id_cseg);
	int		DeleteCSeg(const int id_cseg);	// delete segment index from this vertex
	int	GetNode(void);

private:
	void	GrowDegreeTo(const int max_degree);

private:
	// permanent
	int				id;
	MCMC_Layer_Regions	*player_region;		// pointer to the big graph to which this vertex belongs

	// variables
	float				x,y;
	int				*p_contour_segments;	// all the contour segments that connect to this vertex
	unsigned char		degree;
	unsigned char		Max_Num_Vertex_Degree;

	// contingent
	int				current_cseg;			// current contour segment
};



///////////////////////////////////////////////////////////////
/*This class defines contour segment objects that form regions.
    Given a region Id, all the boundaries could be traced one
	by one.
*/

class MCMC_Contour_Segment :public MCMC_MemoryNode
{
public:
	// construction & destruction
	MCMC_Contour_Segment();
	~MCMC_Contour_Segment();
	void	Empty(void);

	// operators
	MCMC_Contour_Segment &	operator=(const MCMC_Contour_Segment &x);
	friend ofstream &		operator>>(MCMC_Contour_Segment &x, ofstream &strm);
	friend ifstream &		operator<<(MCMC_Contour_Segment &x, ifstream &strm);

	// access
	inline	MCMC_Layer_Regions* LayerRegion(void){return player_region;};
	inline	void	SetLayerRegion(MCMC_Layer_Regions *player_region1){player_region = player_region1;};
	inline	int		KeepCurrent(void){return current_node;};
	inline	void	RestoreCurrent(const int i){current_node = i;};

	inline	int Id(){return id;};
	inline	void SetId(int i){id=i;};
	inline	int		GetLeftAtomicRegion(void){return boundry_of[0];};
	inline	int		GetRightAtomicRegion(void){return boundry_of[1];};
	inline	bool	OnlyTwoNodes(void){if (node[0]==extn[1]) return true;else return false;};			// check weather this contour segment is extremely int
			bool	OnlyTwoNodes(const int id_node1, const int id_node2);
	inline	bool	Valid(void) const {if (node[0]>=0 && node[1]>=0) return true;else return false;}	// valid contour segment?
	inline  bool	SelfClosed(void){if (end[0]==end[1]) return true; else return false;}				// self colosed?
	inline  bool	IsFromNode1ToNode2(MCMC_Node *pnode1, const int id_node1, MCMC_Node *pnode2, const int id_node2);

	void	GetVertices(int &id_ver1, int &id_ver2);	// get the two vertices of this contour segment
	int		GetTheOtherVertex(const int id_ver1);		// get the other vertex other than 'id_ver1'
	int		GetTheOtherRegionId(const int id_region1);		// get the other region other than 'id_region1'
	bool	BelongToAtomicRegion(const int id_region);		// does this region belong to region 'id_region'
	bool	IsOfAtomicRegions(const int iRgn1, const int iRgn2);// Is this contour segment the boundary between region 'iRgn1' and region 'iRgn2'
	bool	IsBoundaryOfGRegion(const int indexid);

	// Is the node 'id_node' the extreme nodes of this contour segment?
	bool	IsEndNode(const int id_node){if (id_node==end[0] || id_node==end[1])return true; else return false;};
	void	Draw(Raster<int> &image,const int value=1);	// Draw this contour segment to image 'image' with value 'value'

	// operations
	int		ReplaceAtomicRegionId(const int id_rgnS, const int id_rgnD);	// replace region label 'id_rgnS' with 'id_rgnD'
	void	SwapVertices(void);											// swap the two extreme vertices
	int		GetNumNode(void);											// get the number of the nodes on this contour segment
	int		GetFirstNode(void);
	int		GetNextNode(void);
	int		GetNextNodeExtn(void);
	int		GetLastNode(void);
	int		GetPrevNode(void);
	bool    PointOfLine(const int x, const int y);						// Is this point on the contour segment?

	double	GetLength(void);
	void	Smooth(void);												// smooth this boundary
	bool	ShowOnPixel(const int id_region, const int id_node);		// used to label regions
	int		GetNextNodeToVertex(const int id_ver);
	void	SetDonotgoRegion(const int id_region){region_donotgo=id_region;}; // set the dangling region into which the tracer doesn't go
	int		GetDonotgoRegion(void){return region_donotgo;};				// get the dangling region into which the tracer doesn't go
	virtual int	TotalCodingBits(void);

	void	ChangeStartOfRelatedRegion();
	void	UpdateTopologyRecord(void);

protected:

private:

	void	DeleteNodesInBetween(const int id_node1, const int id_node2); // delete the nodes in between node 'id_node1' and 'id_node2' in the smooth process
	void	InsertNodesInBetween(const int id_node1, const int id_node2, const bool bjust_one=false);
	void	Simplify(const int id_node1, const int id_node2);
	void	Simplification(const int id_node1, const int id_node2, mcmcMatrix<double> &distances);
	void	DeleteVeryColseNodes(void);

public:
	// variables
	int		boundry_of[2];				//  left and right regions
	int		end[2];						//	two extreme vertices
	int		node[2];					//	two extreme nodes
	int		extn[2];

	// contingent
	int		direction;					//	for tracing the region

private:
	// permanent
	int		id;
	MCMC_Layer_Regions	*player_region;

	// variables
	int		region_donotgo;				// the region that should not go along this segment
	                                        /* -------
                                               |      |
											 __|    ---------
											|       | |      |
											|		 _		 |
											-----------------| */

	// contingent
	int		current_node;				//	for tracing
};

inline bool MCMC_Contour_Segment::IsFromNode1ToNode2(MCMC_Node *pnode1, const int id_node1, MCMC_Node *pnode2, const int id_node2)
{
	if ( ((pnode1->link[0]==id_node2) && !(node[1]==id_node1 && extn[1]==id_node2)) ||
		 (node[0]==id_node1 && extn[0]==id_node2) || 
		 (extn[1]==id_node1 && node[1]==id_node2))
		return true;
	else
		return false;
}




/////////////////////////////////////////////////////////////
/* This class defines nodes' Id temporarily sorted in region
     during the computations of forces on the boundary.
*/
class MCMC_NodeVertex
{
public:
	// construction & destruction
	MCMC_NodeVertex();
	~MCMC_NodeVertex();

	// operators
	MCMC_NodeVertex & operator=(const MCMC_NodeVertex& x);
	virtual bool operator==(const MCMC_NodeVertex& x);

public:
	int			id_node,id_ver,id_cseg;
	McPoint2D	ofOverall,ofStat,ofSmooth;
};

class MCMC_SortedNodes
{
public:
	// construction & destruction
	MCMC_SortedNodes();
	~MCMC_SortedNodes();
	void Empty(void);

	// operator
	MCMC_SortedNodes & operator=(MCMC_SortedNodes &a);
	friend ofstream & operator>>(MCMC_SortedNodes &a, ofstream &strm);
	friend ifstream & operator<<(MCMC_SortedNodes &a, ifstream &strm);

	// operations
	virtual int		GetFirstNode(void)=0;
	virtual int		GetNextNode(void)=0;
	virtual int		NumNodes(void)=0;
	virtual void	SetDirection(void)=0;
	virtual bool	Clockwise(void)=0;
	virtual int		GetCurrentCSeg(void)=0;			// get current contour segment
	virtual int		NumHoles(void) const =0;
	virtual int		GetHole(const int i)=0;

	virtual void	SortAllNodes(void);
	virtual int		GetSortedIndex(const int id_node1);
	virtual int		GetSortedNextNode(const int index);
	virtual int		GetSortedLastNode(const int index);
	virtual int		GetSortedNode(const int index);
	virtual int		GetSortedVertex(const int index);
	virtual int		GetSortedSeg(const int index);
	virtual McPoint2D GetOff(const int index, McPoint2D &ofSt, McPoint2D &ofSm);
	virtual void	SetOff(const int index, const McPoint2D &ofOv, const McPoint2D &ofSt, const McPoint2D &ofSm);
	virtual MCMC_NodeVertex* Get(const int index);
	virtual int		GetFirstIndex(void);
	virtual int		GetNextIndex(void);
	virtual void	GiveUpData(void);
	inline	double	Area(void){return dArea;};
	virtual double	ComputeArea(void);

protected:
	virtual MCMC_Layer_Regions* LayerRegion(void)=0;

	virtual int		GetCorrespondingVertex(const int id_node)=0;

public:
	int				num_node;

protected:
	double			dArea;

private:
	MCMC_NodeVertex		*psorted_nodes;
	MCMC_SortedNodes	**ppcontour_nodes_holes;
	int					index_move;
};
typedef MCMC_SortedNodes* MCMC_PSortedNodes;

////////////////////////////////////////////////////////////////
/* This is a very important class, which associates each region
   with the physical model denoted in 'pmodel'. Different region
   may have differnt actually model derived from the class that
   is inherited from the basic class 'MCMC_Model'.

*/

class MCMC_Region_Stat
{
public:
	// construction & destruction
	MCMC_Region_Stat();
	~MCMC_Region_Stat();
	virtual void DeleteModel(void);

	// operators
	MCMC_Region_Stat & operator=(MCMC_Region_Stat &x);
	friend ofstream & operator>>(MCMC_Region_Stat &x, ofstream &strm);
	friend ifstream & operator<<(MCMC_Region_Stat &x, ifstream &strm);

	// operation
	void SetStat(MCMC_Model *pmodel1);

	double			  GetLogPostProb(const int row_pixel, const int col_pixel);
	virtual double	  EnergyImageModel(void){return pmodel->EnergyImageModel();};
	inline double	  LogLik(void){return pmodel->log_lik;};
	inline MCMC_Model* Model(void){return pmodel;};

protected:
	MCMC_Model		*pmodel;
};

McPoint2D GetOffsetFromNormalAndForces(const double normal_angle,	const double sfs, const double curvature,
									   double* pdStatForce=NULL, double* pdSmoothForce=NULL,
									   McPoint2D* pofStatForce=NULL, McPoint2D* pofSmoothForce=NULL);

class MCMC_FilterResp;

////////////////////////////////////////////////////////////////////
/* This is the core class in this file which defines 'region' objects.
   Each region is the most fundamental component in a graph and has
   many operations associated with.
*/
class MCMC_RegionElement :public MCMC_Region_Stat, public MCMC_SortedNodes
{
public:
	// construction & destruction
	MCMC_RegionElement();
	virtual ~MCMC_RegionElement();

	virtual void	Init(void);
	virtual void	Empty(void);

	// operators
	MCMC_RegionElement& operator=(const MCMC_RegionElement& a);
	friend ofstream & operator>>(MCMC_RegionElement &a, ofstream &strm);
	friend ifstream & operator<<(MCMC_RegionElement &a, ifstream &strm);

	inline	void	SetId(int i){id=i;};
	inline	int		Id(void) const {return id;};
	virtual int		IndexId(void) const=0;
	inline	void	SetIndexIdParent(int i){indexid_parent=i;};
	inline	int		IndexIdParent(void) const {return indexid_parent;};
			int		ToppestLevelIndexId(void);

	inline	void				SetLayerRegion(MCMC_Layer_Regions *player_region1){player_region = player_region1;};
	inline	MCMC_Layer_Regions* LayerRegion(void){return player_region;};
	inline	bool				Valid(void){if (start_cseg<0)return false;else return true;}
	virtual	bool	IsAtomicRegion(void) const {return false;};
	inline	int		GetStartCSeg(void) const {return start_cseg;};
	inline	void	ChangeStartCSeg(const int i){start_cseg=i;};
	virtual bool	UseFirstStartCSeg(void) {return true;};
	virtual bool	UseNextStartCSeg(void) {return false;};
	virtual void	FindTheStartCSeg(void)=0;
	virtual bool	IsTopologyConsistent(void) const {return true;};

	// access
	virtual int		GetFirstCSeg(void);				// get the first contour segment of this region
	virtual int		GetNextCSeg(void);				// get the next contour segment of this region
	virtual int		GetCurrentCSeg(void);			// get current contour segment
	virtual int		GetFirstVer(void);				// get the first vertex of this region
	virtual int		GetNextVer(void);				// get the next vertex of this region
	virtual int		NumAtomicRegions(void){return 1;};
	virtual int		GetFirstNode(void);
	virtual int		GetNextNode(void);
	virtual int		NumNodes(void);

	virtual McPoint2D	Center(void){return pt_center;};

	virtual int		GetFirstAtomicRegion(void)=0;
	virtual int		GetCurrentAtomicRegion(void)=0;
	virtual	int		GetNextAtomicRegion(void)=0;
	__forceinline  int	Direction(void){return direction;};

	virtual bool	GetFirstPixel(int &j, int &i)=0;
	virtual bool	GetNextPixel(int &j, int &i)=0;
	virtual void	LabelFromDomain(Raster<int> &ras_label_map, int id_label);

	// get the next node to the one by id_node1, this is mostly used in diffusion process
	virtual MCMC_Node*		GridGetNextNode(MCMC_Node *pnode, McImagePoint &pt_left_pixel, McImagePoint &pt_right_pixel, const bool bclockwise);
	virtual void			GridGetNeighborNodes(MCMC_Node *pnode, MCMC_Node *p_nodes_left[], MCMC_Node *p_nodes_right[], const int num);
	virtual double			GridGetDiffusionMove(const int id_node1, int &id_node2);
	virtual double			GridGetStatForce(MCMC_Node *pnode, const McImagePoint pt_pixel);
	virtual double			GridGetShapeForce(MCMC_Node *pnode, MCMC_Node *p_nodes_left[], MCMC_Node *p_nodes_right[]);
	virtual double			GridGetTotalForce(MCMC_Node *pnode, const McImagePoint pt_pixel, MCMC_Node *p_nodes_left[], MCMC_Node *p_nodes_right[]);

	// operations
	virtual bool	IsGRegion(void){return true;};
	virtual bool	IsInGRegion(const int id_gregion);
	virtual int		WhichWay(int cseg_last, mcmcVector<int> &vc_csegments);
	virtual void	GetCSetFromVertex(MCMC_Vertex *pver, mcmcVector<int> &vc_csegs, const int id_region, const int side=0)=0;	// side 0: right  1:left)

	virtual void	GetAllAtomicRegions(LinkList<int> &list_aregions)=0;
	
	virtual void	CreateRegionDomain(void)=0; // create the pxiel set for this region
	virtual void	GetRegionDomain(LinkList<PMCMC_PixelSet> &list_domain);

	virtual void	UpdateLowLevelStat(MCMC_FilterResp &resp)=0;

	virtual double	ComputeEnergyShape(void);

	virtual double	GetLength(void)=0;				// get the length of its total boundary
	inline	double	EnergyShape(void){return energy_shapeprior;};
	virtual double	EnergyTotal(void){return EnergyImageModel()+EnergyShape();};
	
	inline double	GetCryingVoice(void){if (pmodel != NULL)return pmodel->crying_voice; else return 0.0;};

protected:
	virtual bool	IsTheSameElement(const int id_aregion1, const int indexid_region2)=0;
	inline void		GridLeftRightRegionId(int &id_region_left, McImagePoint &pt_left_pixel,
										  int &id_region_right, McImagePoint &pt_right_pixel,
										  const int row1, const int col1, const int row2, const int col2);

	virtual double	MinDistToPoints(SimpleMatrix<McPoint2D> &vc_points, const int i);
	virtual double	area(SimpleMatrix<McPoint2D> &vc_points);

public:
	MCMC_AffinityMap			*paffinity_map;
	MCMC_LowLevelStat4Region	*plow_level_stat;


protected:
	// permanent
	int		id;
	MCMC_Layer_Regions	*player_region;

	// variables
	int		start_cseg;						// the index of the starting contour segment
	int		indexid_parent;

	// contingent variables
	int		direction;
	bool		clockwise;						// false:counter clockwise
	int		last_seg;
	int		current_ver;					// current vertex
	int		id_node_temp,id_node_first;		// for tracing all the nodes

	double		energy_shapeprior;
	McPoint2D	pt_center;
};


////////////////////////////////////////////////////////////////////
class MCMC_AtomicRegion :public MCMC_RegionElement, public MCMC_MemoryNode
{
public:

	// construction & destruction
	MCMC_AtomicRegion();
	virtual ~MCMC_AtomicRegion();

	virtual void	Init(void);
	virtual void	Empty(void);

	// operator
	MCMC_AtomicRegion& operator=(MCMC_AtomicRegion& a);
	friend ofstream & operator>>(MCMC_AtomicRegion &a, ofstream &strm);
	friend ifstream & operator<<(MCMC_AtomicRegion &a, ifstream &strm);

	// access
	virtual int					IndexId(void) const{return id;};
	inline	MCMC_Region_Stat&	GetStat(void){return *((MCMC_Region_Stat*)this);};
	inline	void				SetAliveStatus(const bool bal){alive=bal;};
	inline	bool				Alive(void){return alive;};

	virtual void	SetDirection(void);				// false:counter clockwise
	virtual bool	Clockwise(void){return clockwise;};
	virtual	bool	IsAtomicRegion(void) const {return true;};

	virtual void	FindTheStartCSeg(void);

	// operations of hole
	virtual	int		NumHoles(void) const {return holes.Num();};
	virtual int		GetHole(const int i) {return holes.Data(i);};
	inline  int		GetFirstHole(void){return holes.GetFirst();};				// get the first hole of this region
	inline  int		GetNextHole(void){return holes.GetNext();};				// get the next hole of this region
	virtual bool	IsHole(const int id_rgn);		// Is one region its hole?
	virtual bool	AddHole(const int id_rgn);		// add one region to this region as a hole
	virtual int		DelHole(const int id_rgn){return holes.Delete(id_rgn);};		// add one region to this region as a hole
	bool			SegOfHole(const int id_cseg);	// Is boundary 'id_cseg' one of the boundaries of its holes
	inline	void	EmptyHoles(void){holes.Empty();};

	// operations of neighbor
	inline	int		NumNeighbors(void) const {return neighbors.Num();};
	virtual int		GetFirstNeighbor(void) {return neighbors.GetFirst();};// get the first neighboor of this region
	virtual int		GetNextNeighbor(void){return neighbors.GetNext();};	// get the next neighboor of this region
	virtual bool	IsNeighbor(const int id_region_test);
	virtual bool	AddNeighbor(const int id_region_nb);
	virtual bool	DelNeighbor(const int id_region_nb, const int id_region_replace=-1);
	void			DelFromNb(const int id_region_replace);
	inline	void	EmptyNb(void){neighbors.Empty();};

	inline	void	GetCurrentPos(int &id_ver, int & id_seg){id_ver=current_ver;id_seg=last_seg;};
	inline	void	SetCurrentPos(int id_ver, int id_seg){current_ver=id_ver;last_seg=id_seg;};

	virtual int		GetVerNum(void);

	virtual int		GetFirstAtomicRegion(void){return Id();};
	virtual int		GetCurrentAtomicRegion(void){return Id();};
	virtual	int		GetNextAtomicRegion(void){return -1;};

	virtual bool	GetFirstPixel(int &j, int &i){return pixel_set.GetFirst(j, i);};
	virtual bool	GetNextPixel(int &j, int &i){return pixel_set.GetNext(j, i);};

	// operations
	void	MergeSegmentsOfRegion(void);				// rearrange segments, merge segments that have one degree vertex
	int	Label(Raster<int> &ras_label_map, int id_label);
	void	UseDifferentStartCSeg(void);
	int	Stat(Raster_Color<uchar> &raster, const int num_cluster, mcmcMatrix<int> &clustering);
	double	GetBoundLength(void);			// get the length of its outer boundary
	void	ChangeForDiffusion(void);
	void	ChangeBack(void);
	void	CopyRegionInfo(MCMC_AtomicRegion &region, int *pids);
	void	Smooth(void);
	irmm_Rect		GetBound(irmm_Rect *pbound=NULL);	// get the bound for this region

	double			GetNormal(const int index, double &curv,double *pmin_dis=NULL);
	double			GetNormal(const int id_node1, const int id_node, const int id_nod2, double &curv,double *pmin_dis=NULL);
	double			GetStatForce(const int id_node);
	McPoint2D		GetDiffusionMove(const int index, McPoint2D &ofStatForce, McPoint2D &ofSmoothForce);
	McPoint2D		GetDiffusionMove(const int id_node1, const int id_node, const int id_node2, McPoint2D &ofStatForce, McPoint2D &ofSmoothForce);

	virtual int	TotalCodingBits(void);
	virtual void	GetCSetFromVertex(MCMC_Vertex *pver, mcmcVector<int> &vc_csegs, const int id_region, const int side=0);	// side 0: right  1:left)

	virtual bool	IsGRegion(void){return false;};

	void	UpdateTopologyRecord(const bool bupdate_label_map=true);
	virtual void	GetAllAtomicRegions(LinkList<int> &list_aregions);

	virtual void	CreateRegionDomain(void); // create the pxiel set for this region
	virtual void	UpdateLowLevelStat(MCMC_FilterResp &resp);

	virtual double	GetLength(void);				// get the length of its total boundary

protected:
	virtual bool	IsTheSameElement(const int id_aregion1, const int indexid_region2){return id_aregion1==indexid_region2;};

private:
	virtual int		GetCorrespondingVertex(const int id_node);

public:
	MCMC_PixelSet		pixel_set;


protected:
	// variables
	MCMC_DynamicSpace	holes;				// id of its holes
	MCMC_DynamicSpace	neighbors;			// id of its neighbors

	bool				alive;
};

#define RECOMPUTE_ENERGY_SHAPE true
#define DONOT_RECOMPUTE_ENERGY_SHAPE false
///////////////////////////////////////////////////////////

class MCMC_GRegion :public MCMC_RegionElement, public MCMC_MemoryNode
{
public:
	// construcon & destruction
	MCMC_GRegion();
	virtual ~MCMC_GRegion();

	virtual void	EmptyTopology(void);
	virtual void	Empty(void);

	
	// operators
	MCMC_GRegion&	operator=(MCMC_GRegion& a);
	friend ofstream &	operator>>(MCMC_GRegion &a, ofstream &strm);
	friend ifstream &	operator<<(MCMC_GRegion &a, ifstream &strm);

	// access
	virtual int		GetFirstVer(void);
	virtual int		GetNextVer(void);				// get the next vertex of this region
	virtual int		GetCurrentCSeg(void);
	virtual int		GetNextNode(void);
	
	virtual int		IndexId(void) const{return id+SHIFT_GREGION;};
	virtual void	SetDirection(void){;};
	virtual void	SetParentIdForChildRegions(void);

	virtual int		GetFirstAtomicRegion(void);
	virtual int		GetCurrentAtomicRegion(void);
	virtual	int		GetNextAtomicRegion(void);
	virtual int		NumAtomicRegions(void);

	virtual int		GetFirstRegion(void);
	virtual int		GetNextRegion(void);
	inline	int		NumRegions(void) const {return list_indexid.Num();};

	virtual bool	Clockwise(void){return true;};
	virtual int		NumHoles(void) const {return 0;};
	virtual int		GetHole(const int i){return -1;};

	virtual void	GetCSetFromVertex(MCMC_Vertex *pver, mcmcVector<int> &vc_csegs, const int id_region, const int side=0);	// side 0: right  1:left)
	virtual void	FindTheStartCSeg(void);
	virtual bool	UseFirstStartCSeg(void);
	virtual bool	UseNextStartCSeg(void);
	virtual bool	IsTopologyConsistent(void) const {return btopology_consistent;};

	virtual	void	AddRegion(const int indexid);
	virtual void	DeleteRegion(const int indexid);

	virtual bool	GetFirstPixel(int &j, int &i);
	virtual bool	GetNextPixel(int &j, int &i);

	virtual void	GetAllAtomicRegions(LinkList<int> &list_aregions);

	virtual void	CreateRegionDomain(void); // create the pxiel set for this region
	virtual void	UpdateLowLevelStat(MCMC_FilterResp &resp);

	virtual double	GetLength(void);				// get the length of its total boundary
	LinkList<int>*	FindClosedContours(int &num);
	virtual double	ComputeEnergyShape(void);
	virtual double	ComputeEnergyShapeForList(LinkList<int> &list_aregions);

protected:
	virtual bool	IsTheSameElement(const int id_aregion1, const int indexid_region2);
	virtual int		GetCorrespondingVertex(const int id_node){return -1;};
			void	GetMinDistTo(mcmcVector<double> &vc_dist, SimpleMatrix<McPoint2D> &vc_points);

protected:
	// variables
	LinkList<int>	list_indexid;
	LinkList<int>	list_cseg_start;

private:
	int				cseg_start_buf;
	
	LinkList<int>	list_all_cseg;
	bool			btopology_consistent;
};


int IntClose(double x);

class VerticesNear
{
public:
	MCMC_Point	ver0,ver1;
};

class VerticesNearList
{
public:
	void	Insert(MCMC_Point &ver0, MCMC_Point &ver1);
	void	FreeAll(void);
	bool	Exist(MCMC_Point &ver0, MCMC_Point &ver1);
private:
	LinkList<VerticesNear>	list;
};


class MCMC_StartingSeg
{
public:
	// construction & destruction
	MCMC_StartingSeg();
	~MCMC_StartingSeg();

	// operations
	void	Set(MCMC_AtomicRegion &region1, MCMC_AtomicRegion &region2, const bool bAddSegs=true);
	void	Delete(const int id_cseg);
	void	Keep(const int id_cseg);
	void	Add(const int id_cseg);
	int		GetStartingSeg(void);

public:
	int		num_seg;
private:
	mcmcMatrix<int> sign;
	MCMC_AtomicRegion		*pregion1,*pregion2;
	int				id_start_temp;
};

bool ReadFromMalikSegFile(char *fname, Raster<int> &ras_segmentation, char *str_image_id);


inline MCMC_MemoryNode* MCMC_MemoryNodeManagement::GetNode(const int i)
{
	if (i<0 || i>=max_space)
		return NULL;

	switch (by_type)
	{
	case 0: MCMC_Node *p_mnodes;
			p_mnodes = (MCMC_Node*)p_nodes;
			return &(p_mnodes[i]);

	case 1:	MCMC_Vertex *p_vertices;
			p_vertices=(MCMC_Vertex*)p_nodes;
			return &(p_vertices[i]);

	case 2:	MCMC_Contour_Segment *p_csegments;
			p_csegments=(MCMC_Contour_Segment*)p_nodes;
			return &(p_csegments[i]);

	case 3: MCMC_AtomicRegion *p_regions;
			p_regions=(MCMC_AtomicRegion*)p_nodes;
			return &(p_regions[i]);

	case 4: MCMC_GRegion *p_gregions;
			p_gregions=(MCMC_GRegion*)p_nodes;
			return &(p_gregions[i]);
	}
	return NULL;
}

inline int	MCMC_MemoryNodeManagement::GetFirst(void)
{
	current = head;
	return current;
}

inline int	MCMC_MemoryNodeManagement::GetNext(void)
{
	MCMC_MemoryNode *pnode;

	pnode = GetNode(current);
	if (pnode != NULL)
	{
		current = pnode->next;
		return current;
	}
	return -1;
}

////////////////////////////////////////////////////////////
/// to keep track of all the contour segments on the grid
class MCMC_CSegOnGrid
{
public:

	// operators
	MCMC_CSegOnGrid & operator=(const MCMC_CSegOnGrid& a)
	{
		if (this != &a)
		{
			mx_id_cseg_row = a.mx_id_cseg_row;
			mx_id_cseg_col = a.mx_id_cseg_col;
		}
		
		return *this;
	}

	// operations
	void Set(const int height, const int width)
	{
		mx_id_cseg_row.SetDimension(height+1, width);
		mx_id_cseg_row.InitValue(-1);

		mx_id_cseg_col.SetDimension(height, width+1);
		mx_id_cseg_col.InitValue(-1);
	}
	void Clear(void)
	{
		mx_id_cseg_row.InitValue(-1);
		mx_id_cseg_col.InitValue(-1);

		dump = -1;
	}

	inline int& CSegId(const McImagePoint& grid1, const McImagePoint& grid2)
	{
		if (grid1.Row() == grid2.Row())
		{
			if (mx_id_cseg_row.Valid(grid1.Row(), min(grid1.Col(), grid2.Col())))
				return mx_id_cseg_row(grid1.Row(), min(grid1.Col(), grid2.Col()));
			else
			{
				dump = -1;
				return dump;
			}
		}
		else
		{
			assert(grid1.Col() == grid2.Col());
			if (mx_id_cseg_col.Valid(min(grid1.Row(), grid2.Row()), grid1.Col()))
				return mx_id_cseg_col(min(grid1.Row(), grid2.Row()), grid1.Col());
			else
			{
				dump = -1;
				return dump;
			}
		}
	}

	inline int& CSegId(const int j1, const int i1, const int j2, const int i2)
	{
		if (j1 == j2)
		{
			if (mx_id_cseg_row.Valid(j1, min(i1, i2)))
				return mx_id_cseg_row(j1, min(i1, i2));
			else
			{
				dump = -1;
				return dump;
			}
		}
		else
		{
			assert(i1 == i2);
			if (mx_id_cseg_col.Valid(min(j1, j2), i1))
				return mx_id_cseg_col(min(j1, j2), i1);
			else
			{
				dump = -1;
				return dump;
			}
		}
	}


public:
	mcmcMatrix<int>	mx_id_cseg_row;
	mcmcMatrix<int>	mx_id_cseg_col;

private:
	int			dump;
};


#endif
